package com.leetcode.problems94;


import com.leetcode.util.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution01 {


    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> ans = new ArrayList<>();
        inorderTraversal(root,ans);
        return ans;
    }

    public void inorderTraversal(TreeNode root, List<Integer> ans) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(true){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            if(stack.isEmpty()){
                break;
            }
            cur = stack.pop();
            ans.add(cur.val);
            cur = cur.right;
        }
    }
    public static void main(String[] args) {
        System.out.println();
    }
}
